1. Field of the Invention
The invention relates to apparatus, as well as to accompanying methods for use therein, for a large (e.g. approximately 1 Terabit/second), fault tolerant packet switch, particularly suited for asynchronous transfer mode (ATM) communication, which utilizes cell address look-ahead in conjunction with parallel planes of self-routing cross-points, staggered time phased contention resolution and shared memory based input and output modules.
2. Description of the Prior Art
Presently, the growing deployment of the public integrated services digital netword (ISDN) throughout the nationwide telephone system permits each ISDN subscriber to gain access to a communication channel that possesses a significantly increased bandwidth over that available through a conventional telephone (i.e. POTS--plain old telephone services) connection. Although the bandwidth provided by basic rate ISDN service has the potential to provide a wide variety of new communication services to each of its subscribers, in the coming years various communication technologies that are just now emerging, such as broadband video and very high speed data transmission, are expected to impose bandwidth requirements on subscriber ISDN channels that will far exceed the bandwidth obtainable at a basic rate ISDN interface. Such an interface consists of two 64 kbit/second "B" channels and one 16 kbit/second "D" channel, where the "D" channel is a packet channel which carries signalling information for communication occurring over each B channel.
For example, broadband video service offerings might include: desktop teleconferencing having voice/video/data communication from a single terminal located at one's desk, distribution video, video-on-demand, videotelephone, still video picture services and high definition television. In terms of bandwidth, just one high definition television signal is expected to require, depending upon the manner in which it is encoded, at least 45 Mbit/second of channel bandwidth. Clearly, the bandwidth of such a signal far exceeds that furnished by a basic rate ISDN channel.
In an effort to provide sufficient channel bandwidth to meet expected subscriber demand in a public ISDN environment, the art has turned to implementing so-called broadband ISDN (B-ISDN). In B-ISDN, each subscriber channel is presently envisioned as providing an information transfer capacity of approximately 150 Mbit/second. This rate is chosen to provide a minimally sufficient bandwidth at a subscriber interface to simultaneously carry a broadband video service, such as high definition video, and various narrowband services, such as voice transmission. In addition, B-ISDN is also expected to serve as a high speed data transport facility for interconnecting separate local area networks (LANs). Presently, Ethernet based and many other types of LANs generally operate at a gross bit rate of approximately 10 Mbit/second. A proposed LAN, the Fiber Distributed Data Interface, is expected to operate at a gross bit rate of 125 Mbit/second. With this in mind, a bandwidth of 150 Mbit/second currently appears to be sufficiently fast to satisfactorily interconnect a wide variety of different LANs, encompassing those that are currently in use to many of those that are presently being proposed. Furthermore, B-ISDN must also fully accommodate relatively slow ISDN traffic, such as that which occurs at the basic rate.
ISDN involves a marriage of two different transport and switching technologies: circuit switching and packet switching. Circuit switching inherently involves continuously maintaining a real time communication channel at the full channel bandwidth between two points in order to continuously carry information therebetween throughout the duration of a call. Owing to this inherent characteristic, circuit switching can not efficiently accommodate bursty traffic and, for this reason, is generally viewed in the art as being ill suited for use in B-ISDN. Specifically, communication for many services that will occur at relatively low information transfer rates in a B-ISDN environment will appear as periodic bursts when transported over a B-ISDN subscriber channel. In addition, high speed data, such as that occurring over a LAN interconnection, will itself be bursty even apart from the channel. Bursty communications do not require full channel bandwidth at all times. Whenever a circuit switched connection is used to carry bursty traffic, available communication bandwidth that is dedicated to carrying data that occurs between successive bursts, i.e. whenever there is no information to be transferred, is simply wasted. Inasmuch as bursty communications, of one sort or another, are expected to constitute a significant portion of B-ISDN traffic, the significant inefficiencies that would otherwise result from using circuit switched connections to carry bursty traffic through a communication channel generally dictate against using circuit switched connections in a B-ISDN environment.
Despite the inherent limitation on carrying bursty traffic at high efficiencies over circuit switched connections, attempts are still being made in the art to adapt circuit switching to a B-ISDN environment. Nevertheless, while many advances have been and are continuing to be made in circuit switching technology, circuit switching still remains poorly adapted to supporting communication services that occur over widely diverse information transfer rates such as those which are expected to occur in B-ISDN. For example, one attempt advocates overlaying a number of circuit switching fabrics to form a network, with each different fabric operating at a transfer rate of a single prominent broad-or narrowband service. Unfortunately, if this attempt were to be implemented, then segregated switching fabrics would likely proliferate throughout the public telephone network which would disadvantageously and unnecessarily complicate the tasks of provisioning, maintaining and operating the network. Hence, this attempt is not favored in the art. Another attempt in the art aims at providing multi-rate switching. Here, a single group of allocated channels would provide information transport, with each channel providing information transport at a different multiple of a basic transfer rate. A switch would then be dynamically reconfigured, based upon each subscriber's needs, to support specific services therefor that occur at different transfer rates. Unfortunately and disadvantageously, the resulting switch would be considerably more complex than a single rate circuit switch. Furthermore, all channels in a group would need to be synchronized with respect to each other and with no differential delay occurring thereamong. Owing to the need from time to time to switch calls from one physical facility to another as required by network maintenance, maintaining the necessary intra-group synchronization is likely to be quite difficult. As such, this proposal is also not favored. In this regard, see, H. Ahmadi et al, "A Survey of Modern High-Performance Switching Techniques", IEEE Journal on Selected Areas in Communications, Vol. 7, No. 7, September 1989, pages 1091-1103 (hereinafter referred to as the Ahmadi et al publication); and J. J. Kulzer et al, "Statistical Switching Architectures for Future Services", International Switching Symposium ISS'84, Florence, Italy, May 7-11, 1984, Session 43A, paper 1, pages 1-5 (hereinafter referred to as the Kulzer et al publication).
Given the drawbacks associated with circuit switched connections, packet switched connections, specifically using asynchronous transfer mode (ATM), presently appear to be the preferred mode of communication over B-ISDN. This mode involves asynchronous time division multiplexing and fast (high speed) packet switching. In essence, ATM relies on asynchronously transporting information in the form of specialized packets, i.e. so-called ATM "cells". Each ATM cell includes a header followed by accompanying data. The header contains a label, which is used for multiplexing and routing, that uniquely identifies the B-ISDN channel which is to carry that cell between two network nodes. A specific periodic time slot is not assigned to carry a cell on any B-ISDN channel. Rather, once an ATM cell reaches, for example, a B-ISDN switch, fast packet switching occurs: a route is dynamically established through the switch to an output destination for that particular cell followed by transport of the cell over that route, and so on for each successive cell. A route is only established in response to the cell reaching an input of the switch.
Advantageously, ATM communication allows any arbitrary information transfer rate up to the full facility rate to be supported for a B-ISDN service by simply transmitting cells at a corresponding frequency into the network. With ATM, channel bandwidth is dynamically allocated to any B-ISDN call and simply varies with the rate at which cells for that call are applied through a B-ISDN channel. No further intervention is required by either the subscriber or the network itself to utilize differing amounts of available channel bandwidth, as the need therefor arises. Any change in that subscriber's traffic patterns or services, even if dramatic, merely results in a changing mix of cells that are presented to the network for these services and changes in their corresponding rates of occurrence. As long as sufficient bandwidth is available on any subscriber channel to carry all the cells presented thereto, the ATM switching fabric merely continues to route cells to their appropriate destinations and remains essentially unaffected by any such change. Hence, by decoupling the information transfer rates from the physical characteristics of the switching fabric and providing the capability to handle bursty traffic, ATM is particularly well suited to transporting both bursty and continuous bit rate services and is therefore preferred for B-ISDN service. In this regard, see the Kulzer et al publication.
An essential ingredient of B-ISDN is an ATM switch. In order to support B-ISDN, that switch needs to possess the capability of routing cells at an information transfer rate of at least 150 Mbit/second between separate ATM ports. Based upon current estimates, a large central office B-ISDN switch is expected to handle approximately 80,000 subscriber lines each having a 150 Mbit/second channel. With a concentration ratio of 10-to-1, the switch needs to possess a total throughput of approximately 1.2 Terabit/second (1.2.times.10.sup.12 bits/second).
Not surprisingly, a number of different architectures has been proposed in the art for implementing a high speed, e.g. approximately 1 Terabit/second, ATM switch. One such illustrative architecture, which has been widely used in circuit switches, involves the use of a switch that has a single squared matrix of cross-point switching elements. See, e.g. U.S. Pat. No. 4,692,917 (issued to M. Fujoika on Sep. 8, 1987). Advantageously, such switches are internally non-blocking, i.e. once appropriate connections are established for the entire matrix at any given time there will be no contention for any link within that matrix and thereby two cells will not collide therein. However, these switches do suffer from output port contention. This deficiency can be ameliorated somewhat through use of various queuing functions and/or centralized control--though at the expense of significantly increasing switch complexity and cost. More significantly, the cross-point matrix that forms the basis of such a switch has the disadvantageous property of squared growth. Given this growth function, it has been known for some time that a cross-point matrix switch capable of serving a relatively large number of ports is extremely costly to implement. Because of the cost, the art has concluded that a single stage cross-point matrix should be used only in those instances where the packet switch is relatively small or where a relatively small cross-point matrix forms a building block of a large multi-stage switch. In this regard, see pages 1098 and 1099 of the Ahmadi et al publication as well as pages 4 and 5 of the Kulzer et al publication.
In an effort to devise internally non-blocking switching architectures that utilize fewer cross-points than in a single stage crosspoint matrix, the art has devoted considerable attention to use of cascaded interconnection networks that present multi-path switching. One such illustrative architecture involves Batcher-Banyan networks. Examples of Batcher-Banyan based packet switch architectures can be found in the following U.S. patents, all of which are assigned to the present assignee hereof: U.S. Pat. No. 4,910,730 (issued to C. M. Day et al on Mar. 20, 1990--hereinafter referred to as the Day et al '730 patent); U.S. Pat. No. 4,893,304 (issued to J. N. Giacopelli et al on Jan. 9, 1990); U.S. Pat. No. 4,866,701 (issued to J. N. Giacopelli et al on Sep. 12, 1989); U.S. Pat. No. 4,817,084 (issued to E. Arthurs et al on Mar. 28, 1989); U.S. Pat. No. 4,761,780 (issued to B. L. Bingham et al on Aug. 2, 1988); and in the following publications: J. N. Giacopelli et al, "Sunshine: A High performance Self-Routing Broadband Packet Switch Architecture", Proceedings of the XIII International Switching Symposium 1990, Stockholm, Sweden, Paper 21, Vol. III, pages 123-129; T. T. Lee, "A Modular Architecture for Very Large Packet Switches", Proceedings of IEEE Globecom '89, Dallas, Texas, Nov. 1989, pages 1801-1809; and Hui et al, "A Broadband Packet Switch for Integrated Transport", IEEE Journal on Selected Areas in Communications, Vol. SAC-5, No. 8, Oct. 1987, pages 1264-1273. In general, in a Batcher-Banyan based switch, all incoming cells are first routed through a single Batcher sorting network which, in turn, feeds a Banyan routing network. The Batcher network first sorts all simultaneously occurring incoming ATM cells into an ascending order, after which the Banyan routing network routes each of these cells to its addressed destination output port of the switch. Each network is formed of multiple columns of identical Batcher sorting circuits or identical Banyan routing circuits thereby forming respective multi-stage Batcher or Banyan networks. These columns are internally interconnected within each network by binary wiring patterns. Each individual Batcher and Banyan circuit typically has two separate inputs and two separate outputs. A Batcher network may be interconnectd to a Banyan network using a so-called "perfect shuffle" wiring pattern. Incoming ATM cells typically include a header which includes an activity bit followed by address bits. In operation, the Batcher network sorts the incoming cells into ascending order based upon serial comparisons of their destination addresses. In response to these comparisons, each Batcher circuit received two cells simultaneously and assumes either a pass state or a cross state for these two cells. If a Batcher circuit assumes a pass state, then the two cells that are presented to two inputs of that circuit simulatneously appear on corresponding outputs thereof. Alternatively, if that circuit assumes a cross state, then those cells simultaneously appear on the opposite outputs of that circuit. Various Batcher circuits are configured to route that one of the two cells having a higher address to an upper output of each such circuit, while the remaining Batcher circuits are configured to route such cells to the lower output. Similarly, each Banyan circuit decides whether to assume a pass or cross state. However, in lieu of comparing cell addresses as occurs in each Batcher circuit, each Banyan circuit forms its decision for any given cell presented to that circuit based upon the activity bit, to determine cell validity, and a single address bit in that cell. Each Banyan circuit situtated in successive stages of the Banyan routing network serially rotates the address of each incoming cell applied to that circuit by one bit position and then utilizes what is then the most significant bit of the rotated address in forming its decision. Hence, the first column of Banyan circuits operates on the most significant bit of the output port address for each incoming cell applied to the Banyan routing network, while the last column of Banyan circuits operate on the least significant bit of that address.
Other cascaded switch architectures, such as Clos and Benes type networks, that have been proposed in the art rely on using several successive serially connected routing stages, with each stage being implemented using a bus, ring or a shared memory structure. Unfortunately, the routing algorithms that must be followed in these switches to avoid blocking tend to be complex and generally require examining the state of the entire switch before routing decisions can be made. In this regard, see pages 4 and 5 of the Kulzer et al publication. Consequently, these other switch architectures, as presently proposed, are also not suitable for use in implementing an ATM switch for actual B-ISDN service.
In addition, while Batcher-Banyan and other packet switches that rely on cascaded architectures utilize far fewer individual switching circuits than does a crosspoint matrix switch, such cascaded packet switches possess various faults which severely limit their incorporation into an actual operating telephone network. First, because these switches possess highly efficient switching topologies, these switches generally have insufficient redundancies and thereby exhibit very poor fault tolerance. In the event that a single switching circuit in such a packet switch, such as illustratively that described in the Day et al '730 patent, fails, then typically, due to an inherent inability within the switch to route packets around that particular circuit, the entire switch will need to be taken out of service for a period of time during which the fault would be isolated and repaired. Thus, to provide adequate levels of fault tolerance which sufficiently avoid impairments or, in extreme cases, disruption of network switching capacity, the entire cascaded switch might need to be duplicated, with both switches operating, for example, on a well known "hot-standby" basis. Unfortunately, this is an extremely costly solution and hence one that is quite impractical. Second, cascaded switches are extremely difficult to expand. Ordinarily, a basic sized switch is first installed in a network and, as the need arises, is "grown" by successively adding pre-defined increments of switching fabric to continually increase the capacity of that switch in a manner that keeps pace with increasing subscriber demands for services. Unfortunately, the topology of a cascaded switch architecture does not lend itself to incremental growth. In this regard, due to the inflexibility of the switching topology, increasing the size of a cascaded switch generally necessitates a complete re-design and/or replacement of the switching fabric. Hence, a cascaded switch must be initially sized to carry the full switching load that will be expected to occur during its useful life. As such, a local telephone company might likely be faced with significant energy costs in providing B-ISDN service if it were to provide this service through such a cascaded switch. Moreover, the steady state subscriber demand for packet services, specifically B-ISDN, is extremely difficult to estimate, within an acceptable margin of error, prior to the deployment of the services. Accordingly, this difficulty injects sizeable uncertainties into the design and costing of such a switch. Lastly, the high density and complexity of the inter- and intra-switching module interconnect wiring used in a cascaded switch complicates the design of such a switch. It also reduces the physical space that would otherwise be available within a custom integrated circuit(s) for integrating the physical components that are needed to implement each separate switching (e.g. Batcher or Banyan) circuit. Accordingly, by artificially reducing the integration density of the switching circuits used in a cascaded switch, the physical volume and component count of the entire switch both tend to increase thereby again disadvantageously increasing the cost of the switch.
Thus, a need exists in the art for a large, e.g. at least 1 Terabit/second, packet switch particularly suited for use with ATM communication that is relatively inexpensive and simple to implement when compared to packet switches of similar capacity that have been proposed in the art. In addition, the needed packet switch should exhibit a high degree of fault tolerance and be readily and economically expandable on an incremental basis. Advantageously, the emergence of such a switch could well facilitate the provision and deployment of B-ISDN service throughout the public telephone network.